package leetcode.weekly.week347;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

//Solution4Test
public class Solution4 {

	public int maxIncreasingCells(int[][] mat) {
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
		int m = mat.length, n = mat[0].length;
		int[][] visit = new int[m][n];
		List<TreeMap<Integer, List<int[]>>> rows = new ArrayList<>();
		List<TreeMap<Integer, List<int[]>>> cols = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			rows.add(new TreeMap<>());
		}
		for (int i = 0; i < n; i++) {
			cols.add(new TreeMap<>());
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				visit[i][j] = 1;
				int cur = mat[i][j];
				int[] pos = new int[] { i, j };
				rows.get(i).computeIfAbsent(cur, key -> new ArrayList<>()).add(pos);
				cols.get(j).computeIfAbsent(cur, key -> new ArrayList<>()).add(pos);
				queue.add(new int[] { cur, i, j });
			}
		}

		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int val = cur[0], x = cur[1], y = cur[2];
			int t = visit[x][y] + 1;
			Map.Entry<Integer, List<int[]>> rowEntry = rows.get(x).ceilingEntry(val + 1);
			if (rowEntry != null) {
				List<int[]> row = rowEntry.getValue();
				for (int[] r : row) {
					if (t > visit[r[0]][r[1]]) {
						visit[r[0]][r[1]] = t;
					}
				}
			}
			Map.Entry<Integer, List<int[]>> colEntry = cols.get(y).ceilingEntry(val + 1);
			if (colEntry != null) {
				List<int[]> col = colEntry.getValue();
				for (int[] c : col) {
					if (t > visit[c[0]][c[1]]) {
						visit[c[0]][c[1]] = t;
					}
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				ans = Math.max(ans, visit[i][j]);
			}
		}
		return ans;
	}
}
